//#include <iostream>
////#include <string>
////#include <vector>
////#include <list>
////#include <queue>
////#include <deque>
////#include <stack>
////#include <map>
////#include <set>
//#include <cassert>
//using namespace std;
////创建一棵树，必须要先创建树的节点
////创建AVL树的节点
////节点应该包括 指向左右子树的指针；节点存储的值；节点的平衡因子；节点指向父亲节点的指针
////而我们在找到树的节点时，应该可以随意去访问树的左右指针，父指针和内部的元素，所以这里需定义节点为public，struct类默认权限为public
//template <class T>
//struct AVLTreeNode
//{
//    AVLTreeNode(const T& val)
//        : _left(nullptr)
//        , _right(nullptr)
//        , _parent(nullptr)
//        , _bf(0)
//        , _val(val)
//    {}
//    typedef AVLTreeNode<T> Node;
//    Node* _left;
//    Node* _right;
//    Node* _parent;
//    int _bf; /// balance factor
//    T _val;
//};
//
////定义好树的节点，就可以开始定义树，树这里我们就不希望访问树的成员变量，而希望使用成员函数，所以我们设定为class类
//template <class T>
//class AVLTree
//{
//public:
//    typedef AVLTreeNode<T> Node;
//    AVLTree()
//        : _root(nullptr)
//    {}
//
//    //计算高度
//    int Height()
//    {
//        return _Height(_root);
//    }
//
//    //AVL树的验证
//    //要验证一个AVL树，我们就不应该根据bf来判定，因为这是一个毫无疑义的验证方法
//    //当你的bf值记录更新错误，我们还是按照错误的方式来验证的，验证就永远为AVL树
//    //所以我们要根据其左右子树的高度去计算
//    bool AssertAVLTree()
//    {
//        int height = 0;
//        return _AssertAVLTree(_root, height);
//    }
//
//    //中序遍历
//    void InOrder()
//    {
//        _InOrder(_root);
//        cout << endl;
//    }
//
//    //AVL树的插入，要满足二叉搜索树的性质，左孩子小于根，右孩子大于根
//    bool insert(const T& val)
//    {
//        if(_root == nullptr) //空树
//        {
//            _root = new Node(val);
//            if(_root == nullptr)
//                assert(false);
//        }
//        else //不为空树
//        {
//            Node* cur = _root;
//            Node* parent = _root;
//
//            //根据二叉搜索树性质判断插入的位置
//            while(cur)
//            {
//                if(cur->_val < val)
//                {
//                    parent = cur;
//                    cur = cur->_right;
//                }
//                else if(cur->_val > val)
//                {
//                    parent = cur;
//                    cur = cur->_left;
//                }
//                else
//                {
//                    return false;
//                }
//            }
//
//            //插入新节点
//            Node* newnode = new Node(val);
//            if(parent->_val > val)
//            {
//                parent->_left = newnode;
//            }
//            else
//            {
//                parent->_right = newnode;
//            }
//            newnode->_parent = parent;
//
//            //更新平衡因子
//            while(parent)
//            {
//                if(parent->_left == newnode)
//                {
//                    --parent->_bf;
//                }
//                else
//                {
//                    ++parent->_bf;
//                }
//
//                if (parent->_bf == 0)
//                {
//                    break;
//                }
//                else if (parent->_bf == 1 || parent->_bf == -1)
//                {
//                    newnode = parent;
//                    parent = parent->_parent;
//                }
//                else if (parent->_bf == 2 || parent->_bf == -2)
//                {
//                    //旋转
//                    if(parent->_bf == -2 && newnode->_bf == -1)
//                    {
//                        //右单旋
//                        RotationR(parent);
//                    }
//                    else if(parent->_bf == -2 && newnode->_bf == 1)
//                    {
//                       //先左后右
//                        RotationLR(parent);
//                    }
//                    else if(parent->_bf == 2 && newnode->_bf == 1)
//                    {
//                        //左单旋
//                        RotationL(parent);
//                    }
//                    else if(parent->_bf == 2 && newnode->_bf == -1)
//                    {
//                        RotationRL(parent);
//                    }
//                    else;
//
//                    break;
//                }
//                else;
//            }
//
//        }
//        return true;
//    }
//private:
//    Node* _root;
//    void _InOrder(Node* root)
//    {
//        if(root == nullptr)
//            return;
//        _InOrder(root->_left);
//        cout << root->_val << " ";
//        _InOrder(root->_right);
//    }
//    void RotationRL(Node* parent)
//    {
//        Node* pR = parent->_right;
//        Node* pRL = pR->_left;
//        int bf = pRL->_bf;
//
//        //先右单旋
//        RotationR(pR);
//        //后左单旋
//        RotationL(parent);
//
//        if(bf == 1)
//        {
//            pR->_bf = 0;
//            parent->_bf = -1;
//            pRL->_bf = 0;
//        }
//        else if(bf == -1)
//        {
//            pR->_bf = 1;
//            parent->_bf = 0;
//            pRL->_bf = 0;
//        }
//        else
//        {
//            pR->_bf = 0;
//            parent->_bf = 0;
//            pRL->_bf = 0;
//        }
//
//    }
//    void RotationLR(Node* parent)
//    {
//        Node* pL = parent->_left;
//        Node* pLR = pL->_right;
//        int bf = pLR->_bf;
//
//        //先左单旋
//        RotationL(pL);
//        //后右单旋
//        RotationR(parent);
//
//        if(bf == 1)
//        {
//            pL->_bf = -1;
//            parent->_bf = 0;
//            pLR->_bf = 0;
//        }
//        else if(bf == -1)
//        {
//            pL->_bf = 0;
//            parent->_bf = 1;
//            pLR->_bf = 0;
//        }
//        else
//        {
//            pL->_bf = 0;
//            parent->_bf = 0;
//            pLR->_bf = 0;
//        }
//    }
//    void RotationL(Node* parent)
//    {
//        Node* pR = parent->_right;
//        Node* pRL = pR->_left;
//
//        parent->_right = pRL;
//        if(pRL)
//            pRL->_parent = parent;
//        pR->_left = parent;
//        Node* ppnode = parent->_parent;
//        parent->_parent = pR;
//
//        if(parent == _root)
//        {
//            _root = pR;
//            pR->_parent = nullptr;
//        }
//        else
//        {
//            if(ppnode->_left == parent)
//                ppnode->_left = pR;
//            else
//                ppnode->_right = pR;
//            pR->_parent = ppnode;
//        }
//
//        parent->_bf = 0;
//        pR->_bf = 0;
//    }
//    void RotationR(Node* parent)
//    {
//        Node* pL = parent->_left;
//        Node* pLR = pL->_right;
//
//        parent->_left = pLR;
//        if(pLR)
//            pLR->_parent = parent;
//        pL->_right = parent;
//        Node* ppnode = parent->_parent;
//        parent->_parent = pL;
//
//        if(_root == parent)
//        {
//            _root = pL;
//            pL->_parent = nullptr;
//        }
//        else
//        {
//            if(ppnode->_left == parent)
//                ppnode->_left = pL;
//            else
//                ppnode->_right = pL;
//            pL->_parent = ppnode;
//        }
//
//        pL->_bf = 0;
//        parent->_bf = 0;
//    }
//
//
//
//    bool _AssertAVLTree(Node* root, int& height)
//    {
//
//        if(root == nullptr)
//        {
//            height = 0;
//            return true;
//        }
//
//        //计算左子树高度
//        int leftH = 0;
//        //计算右子树高度
//        int rightH = 0;
//        if(!_AssertAVLTree(root->_left, leftH)
//        || !_AssertAVLTree(root->_right, rightH))
//            return false;
//
//
//        if(abs(leftH - rightH) >= 2)
//        {
//            cout << "树高度差超过2" << endl;
//            return false;
//        }
//        else if(rightH - leftH != root->_bf)
//        {
//            cout << "平衡因子数据异常" << endl;
//            return false;
//        }
//
//        height = leftH > rightH ? leftH + 1 : rightH + 1;
//        return true;
//    }
//    int _Height(Node* root)
//    {
//        if(root == nullptr)
//            return 0;
//
//        int left_height = _Height(root->_left);
//        int right_height = _Height(root->_right);
//
//        return left_height > right_height ? left_height + 1 : right_height + 1;
//    }
//};
#pragma once
#include <iostream>
#include<assert.h>
#include<vector>

template<class K, class V>
struct AVLTreeNode
{
    AVLTreeNode<K, V>* _left;
    AVLTreeNode<K, V>* _right;
    AVLTreeNode<K, V>* _parent;
    int _bf; // balance factor
    pair<K, V> _kv;

    AVLTreeNode(const pair<K, V>& kv)
            :_left(nullptr)
            , _right(nullptr)
            , _parent(nullptr)
            , _bf(0)
            , _kv(kv)
    {}
};

template<class K, class V>
class AVLTree
{
    typedef AVLTreeNode<K, V> Node;
public:
    bool Insert(const pair<K, V>& kv)
    {
        if (_root == nullptr)
        {
            _root = new Node(kv);
            return true;
        }

        Node* parent = nullptr;
        Node* cur = _root;
        while (cur)
        {
            if (cur->_kv.first < kv.first)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_kv.first > kv.first)
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                return false;
            }
        }

        cur = new Node(kv);
        if (parent->_kv.first < kv.first)
        {
            parent->_right = cur;
        }
        else
        {
            parent->_left = cur;
        }
        cur->_parent = parent;

        while (parent)
        {
            if(cur == parent->_left)
            {
                parent->_bf--;
            }
            else
            {
                parent->_bf++;
            }

            if (parent->_bf == 0)
            {
                break;
            }
            else if (parent->_bf == 1 || parent->_bf == -1)
            {
                cur = cur->_parent;
                parent = parent->_parent;
            }
            else if (parent->_bf == 2 || parent->_bf == -2)
            {
                // 旋转处理
                if (parent->_bf == 2 && cur->_bf == 1)
                {
                    RotateL(parent);
                }
                else if (parent->_bf == -2 && cur->_bf == -1)
                {
                    RotateR(parent);
                }
                else if (parent->_bf == -2 && cur->_bf == 1)
                {
                    RotateLR(parent);
                }
                else
                {
                    RotateRL(parent);
                }

                break;
            }
            else
            {
                // 插入之前AVL树就有问题
                assert(false);
            }
        }

        return true;
    }

    void RotateL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;

        parent->_right = subRL;
        if(subRL)
            subRL->_parent = parent;

        subR->_left = parent;
        Node* ppnode = parent->_parent;
        parent->_parent = subR;

        if (parent == _root)
        {
            _root = subR;
            subR->_parent = nullptr;
        }
        else
        {
            if (ppnode->_left == parent)
            {
                ppnode->_left = subR;
            }
            else
            {
                ppnode->_right = subR;
            }
            subR->_parent = ppnode;
        }

        parent->_bf = 0;
        subR->_bf = 0;
    }

    void RotateR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;

        parent->_left = subLR;
        if (subLR)
            subLR->_parent = parent;

        subL->_right = parent;

        Node* ppnode = parent->_parent;
        parent->_parent = subL;

        if (parent == _root)
        {
            _root = subL;
            subL->_parent = nullptr;
        }
        else
        {
            if (ppnode->_left == parent)
            {
                ppnode->_left = subL;
            }
            else
            {
                ppnode->_right = subL;
            }
            subL->_parent = ppnode;
        }

        subL->_bf = 0;
        parent->_bf = 0;
    }

    void RotateLR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;

        int bf = subLR->_bf;
        RotateL(parent->_left);
        RotateR(parent);

        if (bf == -1)
        {
            subLR->_bf = 0;
            subL->_bf = 0;
            parent->_bf = 1;
        }
        else if (bf == 1)
        {
            subLR->_bf = 0;
            subL->_bf = -1;
            parent->_bf = 0;
        }
        else if (bf == 0)
        {
            subLR->_bf = 0;
            subL->_bf = 0;
            parent->_bf = 0;
        }
        else
        {
            assert(false);
        }
    }

    void RotateRL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
        int bf = subRL->_bf;

        RotateR(subR);
        RotateL(parent);

        subRL->_bf = 0;
        if (bf == 1)
        {
            subR->_bf = 0;
            parent->_bf = -1;
        }
        else if (bf == -1)
        {
            parent->_bf = 0;
            subR->_bf = 1;
        }
        else
        {
            parent->_bf = 0;
            subR->_bf = 0;
        }
    }

    void _InOrder(Node* root)
    {
        if (root == nullptr)
            return;

        _InOrder(root->_left);
        cout << root->_kv.first << "[" << root->_bf << "]" << endl;
        _InOrder(root->_right);
    }

    void InOrder()
    {
        _InOrder(_root);
    }

    int _Height(Node* root)
    {
        if (root == nullptr)
            return 0;

        int leftHeight = _Height(root->_left);
        int rightHeight = _Height(root->_right);

        return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    }

    int Height()
    {
        return _Height(_root);
    }

    bool _IsBalance(Node* root, int& height)
    {
        if (root == nullptr)
        {
            height = 0;
            return true;
        }

        int leftHeight = 0, rightHeight = 0;
        if (!_IsBalance(root->_left, leftHeight)
            || !_IsBalance(root->_right, rightHeight))
        {
            return false;
        }

        if (abs(rightHeight - leftHeight) >= 2)
        {
            cout <<root->_kv.first<<"不平衡" << endl;
            return false;
        }

        if (rightHeight - leftHeight != root->_bf)
        {
            cout << root->_kv.first <<"平衡因子异常" << endl;
            return false;
        }

        height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;

        return true;
    }

    bool IsBalance()
    {
        int height = 0;
        return _IsBalance(_root, height);
    }

    size_t Size()
    {
        return _Size(_root);
    }

    size_t _Size(Node* root)
    {
        if (root == NULL)
            return 0;

        return _Size(root->_left)
               + _Size(root->_right) + 1;
    }

    Node* Find(const K& key)
    {
        Node* cur = _root;
        while (cur)
        {
            if (cur->_kv.first < key)
            {
                cur = cur->_right;
            }
            else if (cur->_kv.first > key)
            {
                cur = cur->_left;
            }
            else
            {
                return cur;
            }
        }

        return NULL;
    }
private:
    Node* _root = nullptr;
};




























